Insertion Sort List

LeetCode 147 | Difficulty: Medium

Medium

Problem Description

Given the head of a singly linked list, sort the list using insertion sort, and return the sorted list's head.

The steps of the insertion sort algorithm:

- Insertion sort iterates, consuming one input element each repetition and growing a sorted output list.

- At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list and inserts it there.

- It repeats until no input elements remain.

The following is a graphical example of the insertion sort algorithm. The partially sorted list (black) initially contains only the first element in the list. One element (red) is removed from the input data and inserted in-place into the sorted list with each iteration.

Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Constraints:

- The number of nodes in the list is in the range `[1, 5000]`.

- `-5000 <= Node.val <= 5000`

Topics: Linked List, Sorting

---

Approach

Linked List

Use pointer manipulation. Common techniques: dummy head node to simplify edge cases, fast/slow pointers for cycle detection and middle finding, prev/curr/next pattern for reversal.

When to use

In-place list manipulation, cycle detection, merging lists, finding the k-th node.

Sorting

Sort the input to bring related elements together or enable binary search. Consider: does sorting preserve the answer? What property does sorting give us?

When to use

Grouping, finding closest pairs, interval problems, enabling two-pointer or binary search.

---

Solutions

Solution 1: C# (Best: 179 ms)

Metric	Value
Runtime	179 ms
Memory	N/A
Date	2017-10-06

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode InsertionSortList(ListNode head) {
        if(head==null || head.next == null) return head;
        ListNode dummy = new ListNode(Int32.MinValue);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode current = head;
        while (current != null)
        {           
            if (current.next != null && current.next.val < current.val)
            {
                while (pre.next != null && pre.next.val < current.next.val)
                {
                    pre  = pre.next;
                }
                
                ListNode temp = pre.next;
                pre.next = current.next;
                current.next = current.next.next;
                pre.next.next = temp;
                
                pre = dummy;
            }
            else current = current.next;
        }

        return dummy.next;
    }
}

---

Complexity Analysis

Approach	Time	Space
Sort + Process	$O(n log n)$	$O(1) to O(n)$
Linked List	$O(n)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Draw the pointer changes before coding. A dummy head node simplifies edge cases.